Not Applicable.
Not Applicable.
This invention relates to digital data processing systems which compress and decompress digitized analogue signals, such as signals from microphones or other analogue measurement devises. The invention also relates to data processing systems which analyze and monitor digitized analogue signals for diagnostic and display purposes.
Historic Background Of fundamental importance for the digital processing of analogue signals is the so-called Shannon sampling theorem. It was introduced into information theory by C.E. Shannon in the 1940""s. The theorem had been known already to Borel in 1898, according to R. J. Marks II, Introduction to Shannon Sampling and Interpolation Theory, Springer, New York, 1991.
The sampling theorem states that in order to record an analogue signal (such as a signal from a microphone) it is in fact not necessary to record the signal""s amplitude continuously. Namely, if the amplitude of the signal is recorded only at sufficiently tightly spaced discrete points in time then from these data the signal""s amplitude can be reconstructed at all points in time. To this end the spacing of the sampling points is sufficiently tight if it is smaller than half the period of the highest frequency component which possesses a substantial presence in the signal. It is important to note that for Shannon sampling the spacing of the sampling times must be equidistant.
To be precise (see e.g. the text by Marks mentioned above), the reconstruction of the signal from its discrete samples works as follows: Let us denote the maximal frequency in the signal by xcfx89max. Let us further denote the amplitude of the signal at time t by ƒ(t). Assume that a machine measured and recorded the amplitudes ƒ(ti) of the signal at equidistantly spaced points in time, ti, whose spacing xcex94t=ti+1xe2x88x92ti is sufficiently small,             i      .      e      .              xe2x80x83            ⁢      Δ        ⁢          xe2x80x83        ⁢    t     less than             1              2        ⁢                  ω          max                      .  
Then, the amplitude of the analogue signal ƒ(t) at any arbitrary time t can be calculated from the measured values ƒ(tn) in this way:                               f          ⁡                      (            t            )                          =                              ∑            n                    ⁢                                    G              ⁡                              (                                  t                  ,                                      t                    n                                                  )                                      ⁢                          f              ⁡                              (                                  t                  n                                )                                                                        (        1        )            
Here, G(t, tn) is the so-called xe2x80x9ccardinal series reconstruction kernelxe2x80x9d, or xe2x80x9csampling kernelxe2x80x9d:                               G          ⁡                      (                          t              ,                              t                n                                      )                          =                              sin            ⁡                          [                              2                ⁢                                  π                  ⁡                                      (                                          t                      -                                              t                        n                                                              )                                                  ⁢                                  ω                  max                                            ]                                            2            ⁢                          π              ⁡                              (                                  t                  -                                      t                    n                                                  )                                      ⁢                          ω              max                                                          (        2        )            
This method of reconstructing an analogue signal""s amplitude at arbitrary times from only its discretely taken samples can easily be implemented on computersxe2x80x94and it is of course in ubiquitous use.
Shannon Sampling Is Not Optimally Efficient
While this method, xe2x80x9cShannon samplingxe2x80x9d, has been of enormous practical importance, it is clearly not efficient:
When using the Shannon sampling method the highest frequency that is present in the signal determines the rate at which all samples must be taken. Namely, the larger the highest frequency in the signal the more samples must be taken per unit time. This means, in particular, that even if high frequencies occur in a signal only for short durations one must nevertheless sample the entire signal at a high sampling rate.
In practise, it is clear that the xe2x80x9cfrequency contentxe2x80x9d, or xe2x80x9cbandwidthxe2x80x9d, or xe2x80x9cinformation densityxe2x80x9d of common analogue signals is not constant in time and that high frequencies are present often only for short durations. Therefore, it should normally be possible to suitably lower the sampling rate whenever a signal""s information density is low and to take samples at a high rate only whenever the signal""s information density is high. The Shannon sampling method, however, does not allow one to adjust the sampling rate: Shannon sampling is wasteful in that it requires one to first determine the highest overall frequency component in the signal and then, second, to maintain a correspondingly high constant sampling rate throughout the recording of the signal.
This shortcoming of Shannon sampling is important because the sampling rate of digitized analogue signals is usually the major limiting factor for the availability of network transmission speed and for computer memory capacity. Therefore, in order to use data memory and data transmission resources most efficiently, it is highly desirable to find ways to continuously adapt the sampling rate to the varying information density of the signal.
For this purpose, one needs, 1) methods and systems for measuring how a signal""s information density varies in time so that one can adjust the sampling rate accordingly and, 2) methods and systems for reconstructing the signal from its so-taken samples.
Any method that allows one to sample and reconstruct analogue signals at continuously adjusted rates that are lower than the constant Shannon sampling rate amounts to a data compression method.
It would be desirable to be able to implement such a compression method purely digitally: An analogue signal that has been sampled conventionally, i.e. equidistantly (and therefore wastefully), is digitally analyized for its time-varying information density, then digitally resampled at a correspondingly time-varying sampling rate (using the cardinal series sampling formula of above), and is later decompressed by resampling it at a constant high sampling rate using a new sampling kernel that replaces the cardinal series sampling kernel and is appropriate for the case of the time-varying sampling rate.
It is clear that for such a data compression method to be most useful, the quality of the subsequent reconstruction of the signal should be controllable.
It is also clear that means or method for reliably measuring the time-varying information density of analogue signals can also be used for monitoring and displaying the information density of analogue signals. The ability to measure a time-varying characteristic of an analogue signal, such as here the signal""s time-varying information density, can be of great practical value, e.g. for monitoring or diagnostic purposes, as will be explained further below.
The present invention provides corresponding methods and means.
Prior Art Techniques for Adaptive Sampling Rates
Much prior art has strived to achieve methods of sampling and reconstruction which use adaptively lower sampling rates:
Kitamura et al.
The system described by Kitamura, in U.S. Pat. No. 4,370,643 samples signals from analogue at a variable rate. The sampling rate is adjusted according to the momentary amount of change in the signal""s amplitude. The reconstruction quality is not controlled. The system described by Kitamura et al., in U.S. Pat. No. 4,568,912 improves on this by reconstructing the signal as joined line segments. The inventors aim is data compression by adaptive rate sampling and also elimination of quantization noise. However, neither aim is satisfactorily achieved: Large amplitude changes of low bandwidth signals lead to inefficient oversampling rather than to the desired compression. Also, the quantization noise is not effectively eliminated since it tends to reappear in the form of jitter.
Kitamura et al., in U.S. Pat. No. 4,626,827, recognize deficiencies in their prior system. In their new system they determine the variable sampling rate by optionally either zero-crossing counting or by Fourier transforming the signal in blocks. The sampling rates are submultiples of the basic rate.
However, zero-crossing counting is a very unreliable indicator of a signal""s minimum sampling rate: a signal can be very wiggly (and thus information rich) over long intervals without crossing zero at all.
The alternatively described method of establishing the minimum sampling rate by Fourier analysis of a block (or xe2x80x9cintervalxe2x80x9d, or xe2x80x9cslicexe2x80x9d, or xe2x80x9cperiodxe2x80x9d) of the signal is also unreliable. There are two main reasons:
First, there is the well-known time-frequency uncertainty relation. Second, it is known that even low bandwidth signals can be arbitrarily quickly varying in arbitrarily long intervals, and vice versa. Therefore, any method that determines a variable sampling rate by Fourier analysis of blocks of the interval is necessarily prone to uncontrolled instances of over-or undersampling.
Kitamura et al. recognize that there is a problem and try to repair these effects by sending the analogue signal before sampling through a low-pass filter which cuts off at the chosen rate, and there is a similar filter for the output. Also this is not fully satisfactory: The system still amounts to trying to do Shannon sampling for variable rates. However. since Shannon sampling requires constant sampling rates throughout there necessarily arise reconstruction errors wherever the sampling rate changes.
Podolak et al.
The system then described by Podolak et al. in U.S. Pat. No. 4,763,207 works with variable sampling rates, the rates being determined from a set of cascaded lowpass filters. The system which Podolak et al. later describe in U.S. Pat. No. 4,816,829 and U.S. Pat. No. 4,899,146 is similar but does the filtering digitally. In effect, also these systems try to use Shannon sampling for variable ratesxe2x80x94even though it is well-known that Shannon sampling is only correct for strictly constant rates. Indeed, the authors recognize that in their system, in order to reduce uncontrollable errors, the rate must always be held constant for some rather significant length before allowing it to change again.
Similar to Podolak et al. above, Page in U.S. Pat. No. 4,755,795 describes a system in which variable sampling rates are determined by dynamic short-time bandwidth analysis. While Podolak""s method keeps the sampling rate constant for significant stretches of time, Page""s method leads to continuously varying sampling rates. As just discussed above, Podolak keeps the sampling rate constant in stretches because this allows Podolak to provide an approximate decompression method by using the Shannon sampling theorem, whose validity is restricted to constant rates. Page, due to his method""s continuously varying sampling rates cannot use the Shannon sampling theorem for decompression. Indeed, Page is silent on how to decompress, i.e. on how to reconstruct the original signal with controllable error from samples taken at a varying rate.
Johnson et al.
Johnson et al., in U.S. Pat. No. 5,302,950 then describe a system for automatic detection of a signal""s minimum constant sampling rate. This invention works with constant sampling rates and the scope of this invention is merely to provide users with information about memory versus quality options in recording sessions. The determination of the minimum sampling rate is optionally by zero-crossing counting or by block-wise Fourier transform.
Johnson et al., in U.S. Pat. No. 5,543,792 then build on this method. They describe a system which does data compression again by effectively doing Shannon sampling at block-wise constant rates. This system therefore too suffers from the above mentioned deficiencies. In particular, for the reconstruction purposes this system establishes a common time base of the various rates used. This is to fill in, i.e. to restore the samples previously dropped in the compression process. However, it is known that the reconstruction of lost samples requires some significant oversamplingxe2x80x94because the reconstruction of lost samples is numerically highly unstable under small perturbations.
In addition, their methods of zero-crossing counting or Fourier transform in blocks for the purpose of determining the sampling rate suffers again of the above mentioned deficiencies. The system also does not provide control over the quality of the reconstruction.
In Johnson et al., U.S. Pat. Nos. 5,610,825 and 5,893,899 the authors add a system for informing users of potential information loss through undersampling. However, the method is not measuring the actual reconstruction quality. Instead, it merely compares the actual sampling rate to a theoretical rate. The theoretical rate is determined again by methods such as Fourier transform in blocks, the reliability of which is limited due to the above mentioned reasons.
Systems Using Psychoacoustic and Psychovisual Effects
Systems of the type described e.g. by Anderson in U.S. Pat. No. 5,388,181 utilize peculiarities of human perception, i.e. certain psychoacoustic and psychovisual effects. These methods compress data by dropping such information the loss of which humans are normally not likely to perceive. Such systems are limited to analogue signals which are audio or video signals, and among these only to those signals for which high quality reconstruction is inessential. Due to their loss of information such compression systems are unsuitable, e.g., for the compression of most medical and scientific analogue signals.
Prior Art Which Measures Signals"" Variable Information Density for Monitoring and Diagnostic Purposes
Methods for measuring a signal""s varying information density are useful not only for data compression purposes. Methods for measuring a signal""s varying information density can also be a valuable tool for the technical and medical monitoring of the source of the analogue signal:
For example, it has been found that often characteristics of sounds emitted by machines change shortly before the machine fails. Similarly, much effort is put into the analysis and monitoring of seismic signals for changes which might indicate imminent quakes. The monitoring of signal characteristics has also proven useful in medical applications, for example in efforts to predict epileptic seizures from patients"" EEG signals. Current methods and applications are described, e.g., in L. Cohen, Time-frequency analysis, Prentice Hall, 1995.
In prior art, methods which monitor signals by measuring the signals"" varying information density use the same approaches as discussed before in the context of data compression, such as zero crossing counting and various windowed Fourier transforms. These methods therefore possess the same deficiencies as discussed above in the context of data compression.
Limitations of Prior Art
To summarize, prior art methods and systems do not reliably measure the analogue signals"" time-varying information density. Therefore, prior art does not provide means or methods for optimally adjusting the sampling rate to the varying information density of signals. Therefore, prior art adaptive rate sampling does not yield efficient data compression. Prior art also does not provide efficient means or methods for decompressing data sampled at varying rate because prior art does not allow the user to satisfactorily control the amount and type of compression loss, namely, prior art does not allow the user to satisfactorily control the amount of possible deviation of the decompressed signal (i.e. of the reconstructed signal) from the original signal.
The present invention comprises a digital method for measuring a digitized analogue signal""s varying information density. This part of the invention can stand alone, i.e. it alone is already useful. Namely, it provides a new method for monitoring how an important characteristic of analogue signals, namely their information density, varies over time. This monitoring ability can be useful both for technical and medical diagnostic purposes.
Based on this method for measuring the variable information density of signals, the present invention further comprises a digital method for compressing and decompressing digitized analogue signals. Namley, according to the present invention, 1) a signal""s samples taken conventionally at a constant high rate are input, 2) the signal""s time-variable information density is measured digitally, 3) the signal is numerically resampled from these samples taken at the constant high sampling rate to samples at a continuously variable lower sampling rate which corresponds to the measured time-varying information density and 4) those lower rate samples (and the rate information) are output as the compressed data. 5) The invention also provides a method for reconstructing the original signal from this output by using a new sampling kernel that replaces the usual cardinal series sampling kernel.
It is an object of the invention to thereby provide a method for approaching the theoretical limit of compression. It is a further object of the invention that it provides the user with full control over the amount and type of lossyness of the compression, i.e. over the quality of the reconstructed signal.
According to the present invention, the time-varying information density of analogue signals is measured by applying a line search algorithm. This new method has the important advantage that the sampling rate is adjusted truly continuously, thus adjusting optimally to the signal and avoiding the block boundary artifacts of prior art. The line that the algorithm searches for is the maximum sample spacing as a function of time. In the line search algorithm, trial time-varying sampling rates are systematically tried out and labeled acceptable if, for the signal at hand, an acceptance criterion calculated from the signal and the trial sampling rate is met. A preferred embodiment of a line search algorithm is explicitly given.
Also, several explicit embodiments of acceptance criteria are given. The preferred embodiment of an acceptance criterion is the criterion whether the reconstruction with a preferred choice of reconstruction kernel yields a reconstructed signal of predetermined maximum deviation from the original signal. This embodiment has the important advantage that it provides the user with full control over the amount of lossiness of the compression. The invention allows the use of arbitrary choices of functions G(t,tn) as the reconstruction kernel for time-varying sampling rates. A preferred choice of G(t,tn) is presented, which is optimal according to the present inventor""s analysis. The line search outputs the lowest time-varying sampling rate that meets the acceptance criterion. The compression can be iterated, e.g. with successive levels of required reconstruction quality applied to the difference between the original and the reconstructed signals of the previous compression step.
For the underlying idea, please see the section xe2x80x9cTheory of Operationxe2x80x9d, below.